package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: parenthesesValid
 * @author: chanzhugang
 * @create: 2022/06/05 09:35
 */
public class ParentheseValid {

    /**
     * 20. 有效的括号
     * 消消乐/连连消问题
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        // 遍历字符串，字符如果是左括号，压入栈；如果是右括号，和栈顶元素比较是否相等
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    // 没有左括号
                    return false;
                }
                // 右括号取栈顶元素
                Character popC = stack.pop();
                if (c == ')' && popC != '(') {
                    return false;
                }
                if (c == ']' && popC != '[') {
                    return false;
                }
                if (c == '}' && popC != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}